package arithmetic;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Author: Jie
 * @Date: 2019/1/24 10:33
 * @Function :169 求众数
 *
 * Given an array of size n, find the majority element.
 * The majority element is the element that appears more than ⌊ n/2 ⌋ times.
 *
 *
 * 1、思路一 map 技术暴力法   时间 on 空间 on
 * 2、思路二 排序nlogn，记录下标计数  时间 on 空间 o1
 * 3、 计数不排序  2层循环 O n^2
 * 4、分治算法   NlogN 2遍找 左 右  那边大返回哪边，最后比较是否大于n/2
 */
public class A_12_MajorityElement {
    public static void main(String[] args) {
        int result = majorityElement(new int[]{3,2,3});
        System.out.println("print result == "+result);

//官网答案
//        Arrays.sort(nums);
//        return nums[nums.length / 2];  eg: 1 1 2    1 2 2  奇数 3/2 =1  小标是1 刚好是一半那位
//        return nums[nums.length / 2];  eg: 1 1 1 3   0 2 2 2  偶数 4/2 =2  小标是1 刚好是一半 + 1位 。
    }

    //  2、思路二 排序nlogn，记录下标计数  时间 on 空间 o1
    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int countMax = 0;
        int numMax = 0;
        int reultCount = nums.length / 2;
        int countNow=0;
        int numNow=nums[0];
        for (int i = 0; i < nums.length; i++) {
           int num = nums[i];
            if (num==numNow){
                countNow++;
            }else {
                if (countNow>reultCount){
                    return numNow;
                }
                //下一个数
                if (countNow>countMax){
                    countMax = countNow;
                    numMax = numNow;
                }
                countNow=0;
                numNow=num;
                countNow++;
            }
        }
        //最后一个数
        if (countNow>countMax){
            countMax = countNow;
            numMax = numNow;
        }

        return numMax;
    }

    //LeetCode_5ms  未知。。。O n

    /**
     * 摩尔投票法的基本思想，
     * 在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。
     * 这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。
     * 如果只存在一种元素，那么这个元素则可能为目标元素。
     * @param nums
     * @return
     */
    public static int majorityElementLeetCode_5ms(int[] nums) {
        //注意：摩尔投票法，重要前提！！！众数一定存在，即一个数出现次数多于一半
        int res = 0, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {res = num; ++cnt;}
            else if (num == res) ++cnt;
            else --cnt;
        }
        return res;
    }
}

